class Solution(object):
    def insert(self, head, insertVal):
        """
        :type head: Node
        :type insertVal: int
        :rtype: Node
        """
        if not head:
            head = Node(insertVal)
            head.next = head
            return head
        else:
            virtual_head = Node(0, head)
            flag = False
            prev = virtual_head
            node = head
            insertnode = Node(insertVal)
            count = 0
            more_diff = float('inf')
            more_flag = False
            less_diff = float('inf')
            less_flag = False
            while True:
                if node == head:
                    count += 1
                    if count == 2:
                        if less_flag:
                            search_value = insertVal - less_diff
                        else:
                            search_value = insertVal + more_diff
                if count == 1:
                    if node.val >= insertVal:
                        more_diff = min(more_diff, node.val - insertVal)
                        more_flag = True
                    else:
                        less_diff = min(less_diff, insertVal - node.val)
                        less_flag = True
                if count == 2:
                    if less_flag:
                        if prev.val == search_value and node.val != search_value:
                            prev.next = insertnode
                            insertnode.next = node
                            break
                    else:
                        if prev.val != search_value and node.val == search_value:
                            prev.next = insertnode
                            insertnode.next = node
                            break
                if count == 3:
                    insertnode.next = head.next
                    head.next = insertnode
                    break
                prev = node
                node = node.next
            return virtual_head.next